1. Field of the Invention
The present invention generally relates to data compaction by the recognition and detection of repeated patterns in either data or physical characteristics described by such data and, more particularly, to the compaction of data descriptive of shapes into which a pattern of, for example, conductive material may be dissected for purposes of reproduction under automated machine control.
2. Description of the Prior Art
Many manufacturing processes include a significant number of repeated sequences of actions. Particularly in the semiconductor industry, a particular pattern of more or less high complexity will be reproduced many times on the same wafer by a step-and-repeat procedure. While such a step-and-repeat process often involves an exposure of a sensitized surface to radiation with the pattern established by a mask, the same type of operation could readily be performed by a direct write operation using light (e.g. from a laser) or an electron beam. In this latter case, the amount of data required for reproduction of the entire pattern (or a portion thereof since more than one pattern could contribute to the entire final pattern) by repetitions of a basic pattern is reduced by an amount equal to the product of the number of repetitions of the pattern and the amount of data required to describe the basic pattern, usually leading to significant data reductions.
In modern semiconductor integrated circuit manufacturing processes, lithographic techniques are often employed to develop patterns which will form the various circuit elements of an integrated circuit and connections therebetween. While a plurality of chips may be formed on a wafer by a step and repeat exposure for each chip or each portion thereof at the chip level, desired patterns of the chip, itself, are often formed by dissection of the pattern into abutting elemental areas, predominantly rectangular in shape, and using an automated exposure tool to form each elemental shape in a high-speed sequence of individual exposures in response to numerical control data (NCdata).
However, as integrated circuits have become more complex and constructed at higher densities and smaller feature sizes, the number of such elemental areas has become very large, often requiring hundreds of thousands if not millions of exposures. In the past, this number of elemental areas was often reduced to more manageable numbers by limiting proximity correction (exposure correction for the exposure "dose" an area may receive due to certain imperfections in the exposure system such as secondary emission and other electron scattering effects in electron beam lithography exposure tools) and assigning a common dose to many contiguous elemental areas which can then be produced by a plurality of step and repeat operations at the same dose in order to form a continuous shape. In such a case, the step and repeat operations can be directly defined from shape length and can be assumed without detection if the rectangle has a dimension greater than an optimum spot size (maxspot) of the tool.
A further complicating factor, particularly in regard to e-beam tools is the fact that materials which are sensitive to e-beam exposure will exhibit "blooming", if overexposed; causing loss of precision in the location of edges of the pattern. Therefore, even though shapes may be repeated with great regularity in some patterns, it is likely that individual spots in any sequence of spots will require different exposure doses and thus cannot be produced by a regular step-and-repeat procedure.
While it is desirable to "saturate" or fully expose resist or other exposure-sensitive materials to obtain full contrast for the pattern but recognizing the tendency of such materials to exhibit "blooming" if overexposed, a proximity correction system and methodology has been developed, as disclosed in U.S. patent application Ser. No. 08/010,715, filed Jan. 29, 1993, by Stuart et al., which is assigned to the assignee of the present invention and fully incorporated by reference herein. This technique compensates for the potential for overexposure of areas due to secondary emission and scattering effects in e-beam tools from neighboring exposed areas of the pattern (referred to as proximity correction) so that elemental areas can be correctly exposed (e.g. fully proximity corrected to any desired degree of exposure accuracy) while still maintaining the volume of data to a minimum. This technique, however, because of the greater exposure accuracy provided, increases the number of rectangles (e.g. each rectangle being composed of one or more elemental rectangular areas having the same computed exposure dose) over the prior, less accurate techniques of limited proximity correction in which simplifying assumptions are employed to limit the data volume.
This increase in the number of areas receiving different doses infers a similar increase in the number of rectangle descriptions and a decrease in the number of contiguous step-and-repeat operations possible at the same dose. Also, improved accuracy of proximity correction during tiling or filling of areas, such as near the borders of pads and conductor runs in the vicinity of pads, under stringent design rules, implies a likelihood of similar elemental area exposures which are not contiguous at a particular exposure dose and for which no efficient or effective detection or data compaction technique currently exists. Accordingly, the problem of manipulation of a great quantity of data with sufficient speed to control an exposure tool with throughput sufficient to a manufacturing application remains very difficult.
Regardless of how the final pattern is ultimately achieved, a basic pattern must be formed. In present-day integrated circuits of high complexity and integration density an initial layout pattern for a mask or other physical pattern to be produced is preferably directly written into a resist coating on a wafer or other material from which a mask is to be formed by a tool such as an electron beam lithography exposure apparatus, hereinafter referred to as an e-beam tool (or, more generally, "exposure tool"). Whether the exposure is by an electron beam or other form of energy, the exposure tool directs such energy at high speed to a long sequence of very small areas on the surface to be exposed under automated control and thus builds up a pattern from a large plurality of exposed (generally rectangular) spots. These spots will be located in accordance with the design of the pattern and also have particular addresses corresponding to a corner, center or other location in accordance with some convention. Otherwise, the spots must be considered as being randomly located for generality of reproducible patterns.
In view of the complexity of present-day integrated circuits, a basic pattern may include tens or hundreds of millions of such exposure spots. Therefore, while the description of such spots may be relatively simple in comparison with even a simple basic pattern, the number of spots to be exposed constitutes an enormous volume of data for each pattern. When it is considered that each byte of such data must be transferred to at least one register is order to control the exposure tool and that such transfer requires a finite amount of time, it can be understood that the volume of data needed to define a basic pattern can easily cause a substantial amount of processor overhead unless some data compaction is possible. Further, the amount of storage required for a list of the exposure spots often limits the number of patterns which may be cost-effectively stored in memory of an automated exposure tool.